#include "BTreeNode.h"
#include <math.h>
#include <iostream>

using namespace std;

int MAX_LEAF_ENTRIES(){
    return (PageFile::PAGE_SIZE-4)/12;
}
int MAX_NONLEAF_ENTRIES() {
    return (PageFile::PAGE_SIZE-4)/8;
}

BTLeafNode::BTLeafNode(){
	//buffer = new char[PageFile::PAGE_SIZE];
	memset((void*)&buffer,0,PageFile::PAGE_SIZE);
	numKeys=0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf) {
	memset((void*)&buffer,0,PageFile::PAGE_SIZE);
	int retval = pf.read(pid, &buffer);
	//compute numkeys
	if (retval == 0) {
		int i;
		for ( i = PageFile::PAGE_SIZE-5; i >= 0; i--){
			if (buffer[i] != 0) {
				break;
			}
		}

		if (i == 0) {
			numKeys = 0;
		} else {
            if (i%12 == 0 && i !=0) {
                numKeys = i/12;
            } else {
                numKeys = i/12 + 1;
            }
		}
	}

	return retval;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf) {
	return pf.write(pid,&buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount() { 
	return numKeys; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid) {

	if (numKeys < MAX_LEAF_ENTRIES()) {
		// find location to insert
		int loc = -1;
		for (int i = 0; i < numKeys; ++i) {
			if (key <= readKey(i)) {
				loc = i;
				break;	
			}
		}
		// if loc not found append the new record
		if (loc == -1) {
			memcpy((void*)&buffer[(numKeys * 12)], &rid, 8);
			memcpy((void*)&buffer[(numKeys * 12)+8], &key,4);
		} else {
			//shift bytes then insert
			int numToShift = numKeys - loc;
			char *temp = (char *)malloc(numToShift*12);
			if (!temp){
				return -1;
			}
			//save old key/rid
			memcpy((void*)temp,(void *)&buffer[loc*12],numToShift*12);

			//copy new values
			memcpy((void*)&buffer[(loc * 12)], &rid, 8);
			memcpy((void*)&buffer[(loc * 12)+8], &key,4);

			//copy old values
			memcpy((void *)&buffer[((loc+1)*12)],(void*)temp,numToShift*12);
			free(temp);
		}

		numKeys++;
		return 0; 
	} else {
		return -1;
	}
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey) {

	int numLeft = (int) ceil((numKeys+1.0)/2.0);
	int numRight = (numKeys + 1) - numLeft;

	int loc;
	locate(key, loc);

	if (loc < numLeft) {
		//spilt numleft -1 nodes into the original
		//move the remaining into the new node
		memcpy((void*)&sibling.buffer, (void*)&buffer[(numLeft-1)*12], numRight*12);
		memset((void*)&buffer[(numLeft-1)*12],0,numRight*12);
        numKeys--;
		insert(key,rid);
        numKeys = numLeft;
        sibling.numKeys = numRight;
        
		//copy our left ptr into the sibling
		memcpy((void*)&sibling.buffer[PageFile::PAGE_SIZE-4],(void*)&buffer[PageFile::PAGE_SIZE-4],4);
    
		siblingKey = sibling.readKey(0);
	} else {
		// split numleft into original
		// split remaining into new node
		// insert into new node
		memcpy((void*)&sibling.buffer, (void*)&buffer[(numLeft)*12], (numRight-1)*12);
		memset((void*)&buffer[(numLeft)*12],0,(numRight-1)*12);
		sibling.insert(key,rid);
        numKeys = numLeft;
        sibling.numKeys = numRight;
        
		//copy our left ptr into the sibling
		memcpy((void*)&sibling.buffer[PageFile::PAGE_SIZE-4],(void*)&buffer[PageFile::PAGE_SIZE-4],4);
		siblingKey = sibling.readKey(0);
	}

	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid){ 	
	int loc = -1;
	for (int i = 0; i < numKeys; ++i) {
        int temp = readKey(i);
		if (temp >= searchKey) {
			loc = i;
			break;	
		}
	}

	if (loc != -1) {
		eid = loc;
		return 0;
	} else {
        eid = numKeys;
		return -1;
	}

}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid) {
	//grab rid
	if (eid < numKeys) {
		// memcpy(&key,(void*)&buffer[(eid*12)+8],4);
		key = readKey(eid);
		memcpy(&rid.pid,(void*)&buffer[(eid*12)],4);
		memcpy(&rid.sid,(void*)&buffer[(eid*12)+4],4);
		return 0;
	} else {
		return -1;
	}
 }

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr() {
	int eid = PageFile::PAGE_SIZE-4;
	int key;
	memcpy(&key,(void*)&buffer[eid],4);
	return key;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid) { 
	int eid = PageFile::PAGE_SIZE-4;
	memcpy((void*)&buffer[eid], &pid, 4);
}

int BTLeafNode::readKey(int eid){
	if (eid<numKeys){
		int key;
		memcpy(&key,(void*)&buffer[(eid*12)+8],4);
		return key;
	}
}
void BTLeafNode::dumpNode(){
	cout << numKeys << ": | ";
	int idx = 0;
	for (int i = 0; i < numKeys*12; i+=4) {
		if (idx%3 == 0) {
			cout << "p" <<((int*)buffer)[i/sizeof(int)] << " | ";
		} else if (idx%3 == 1) {
			cout << "s" <<((int*)buffer)[i/sizeof(int)] << " | ";
		} else {
			cout <<((int*)buffer)[i/sizeof(int)] << " | ";
		}
		idx++;
	}
	cout << getNextNodePtr() << endl;
}


BTNonLeafNode::BTNonLeafNode(){
	memset((void*)&buffer,0,PageFile::PAGE_SIZE);
	numKeys=0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf) { 
	memset((void*)&buffer,0,PageFile::PAGE_SIZE);
	int retval = pf.read(pid, &buffer);
	//compute numkeys
	if (retval == 0) {
		int i;
		for ( i = PageFile::PAGE_SIZE-1; i >= 0; i--){
			if (buffer[i] != 0) {
				break;
			}
		}

		if (i == 0) {
			numKeys = 0;
		} else {
			if (i%8 == 0 && i !=0) {
                numKeys = i/8;
            } else {
                numKeys = i/8 + 1;
            }
            
		}
	}

	return retval;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf) { 
	return pf.write(pid,&buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ return numKeys; }


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */



RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	if (numKeys < MAX_NONLEAF_ENTRIES()) {

		int loc = -1;
		for (int i = 0; i < numKeys; ++i) {
			if (key <= readKey(i)) {
				loc = i;
				break;	
			}
		}

		if (loc == -1) {
				memcpy((void*)&buffer[(numKeys *8)+4], &key,4);
				memcpy((void*)&buffer[(numKeys *8)+8], &pid, 4);
		} else {
			//shift bytes then insert
			int numToShift = numKeys - loc;


			char *temp = (char*)malloc(numToShift*8);
			if (!temp){
				return -1;
			}

			memcpy((void*)temp,(void*)&buffer[(loc*8)+4],numToShift*8);
			memcpy((void*)&buffer[(loc*8)+4], &key,4);
			memcpy((void*)&buffer[(loc*8)+8], &pid,4);

			memcpy((void*)&buffer[((loc+1)*8)+4],(void*)temp,numToShift*8);
			free(temp);
		}

		numKeys++;
		return 0; 
	} else {
		return -1;
	}
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey) {

	char temp[PageFile::PAGE_SIZE+8];
	if (!temp){
		return -1;
	}

	memcpy((void*)&temp,(void*)&buffer,(numKeys*8)+4);

	int loc = -1;
	for (int i = 0; i < numKeys; ++i) {
		if (key <= readKey(i)) {
			loc = i;
			break;	
		}
	}

	if (loc == -1) {
			memcpy((void*)&temp[(numKeys *8)+4], &key,4);
			memcpy((void*)&temp[(numKeys *8)+8], &pid, 4);
	} else {
		//shift bytes then insert
		int numToShift = numKeys - loc;

		memcpy((void*)&temp[(loc*8)+4],&key,4);
		memcpy((void*)&temp[(loc*8)+8],&pid,4);

		//save old key/rid
		memcpy((void*)&temp[((loc+1)*8)+4],(void*)&buffer[(loc*8)+4],numToShift*8);
	}

	memset((void*)&buffer,0,PageFile::PAGE_SIZE);

	int numLeft = (numKeys+1)/2;
	int numRight = numKeys - numLeft;
	memcpy((void*)&buffer,(void*)&temp,(numLeft*8)+4);
	memcpy((void*)&sibling.buffer,(void*)&temp[((numLeft+1)*8)],numRight*8+4);
	int eid = (numLeft*8)+4;
	memcpy(&midKey,(void*)&temp[eid],4);

	numKeys = numLeft;
	sibling.numKeys = numRight;

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid) { 
	
	if(numKeys == 0){
		return -1;
	}

	int loc = -1;
	for (int i = 0; i < numKeys; ++i) {
		if (readKey(i) > searchKey) {
			loc = i;
			break;	
		} else if (readKey(i) == searchKey){
			loc = i+1;
			break;
		}
	}
	int eid = loc*8;
	if (loc == -1) {
		eid = numKeys*8;
	}
	memcpy(&pid,(void*)&buffer[eid],4);
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2) {
	memset((void*)&buffer,0,PageFile::PAGE_SIZE);
	memcpy((void*)&buffer,&pid1,4);
	memcpy((void*)&buffer[4],&key,4);
	memcpy((void*)&buffer[8],&pid2,4);
	numKeys = 1;

	return 0;
}


int BTNonLeafNode::readKey(int eid){
	if (eid<numKeys){
		int key;
		memcpy(&key,(void*)&buffer[(eid*8)+4],4);
		return key;
	}
}

void BTNonLeafNode::dumpNode(){
	cout << numKeys << ": | ";
	int idx = 0;
	for (int i = 0; i < (numKeys*2+1)*4; i+=4) {
		if (++idx%2) {
			cout << "p" <<((int*)buffer)[i/sizeof(int)] << " | ";
		} else {
			cout << ((int*)buffer)[i/sizeof(int)] << " | ";
		}
	}
	cout << endl;
}

PageId BTNonLeafNode::pageIdAt(int eid){
	PageId pid;
	memcpy(&pid,(void*)&buffer[(eid*8)],4);
	return pid;
}
